1. Field of the Invention
The present invention is related to the field of routing algorithms through networks, and more specifically to devices, software and methods of network routing based on Quality of Service that accounts for the nature of packet loss.
2. Description of the Related Art
Networks, such as the internet, are increasingly used for transmitting voice data and image data. Network transmission is now described in more detail.
Referring to FIG. 1, a network 120 is shown having nodes A, B, C, D, E, F, G, H, I, J, K, L, M, N, P, Q, R. Between some (but not all) pairings of these nodes there are communication links. It will be appreciated that the links are intimately associated with the nodes they terminate in.
At each one of these nodes there is a network router, or switch, etc. An example is described below.
Referring to FIG. 2 a router 210 at node N of FIG. 1 is described. Router 210 has a central Processing Unit (CPU) 220 and a memory 230. Memory 230 is controlled by CPU 220. Memory 230 is also called a queue, and typically has a certain capacity.
Packets arrive at node N from any source, and are stored in memory 230. Then they are retransmitted from memory 230. The packets arrive and are stored in a sequence, but may be retransmitted according to a different sequence, depending on their priority. Ordinarily the stored packets are retransmitted before the queue becomes full.
Returning to FIG. 1, when a request for a flow of data arrives, it defines the two endpoints. In the example of FIG. 1, there is a request to transmit data from a sender S to a receiver V. The two endpoints are node A (the first receiver for sender S) and node R (the final transmitter for receiver V).
As data travels from endpoint sender S to endpoint receiver V, a path is defined between nodes within the network. The path is along various nodes of the network. In the example of FIG. 1, a path 150 is defined via nodes A, E, J, N, R of network 120.
The diagram of FIG. 1 is simplified, in that it shows data flowing only one way. In many instances, however, there is also a return path for the data to flow in the reverse way, such as for two-way telephone and video conferences. The return path may or may not be the same as path 150.
The so-called routing problem is to decide which nodes the data flow should be routed through. The routing problem is solved by routing algorithms. Such algorithms are addressed by a body called the Internet Engineering Task Force (IETF). At the time of the original filing of this document with the U.S.A. Patent Office, the IETF maintains a website at <www.ietf.org>.
Within the context of IETF, document RFC-2386 points out that routing may be based on considerations such as Quality-of-Service (QoS). QoS is a set of service requirements that are to be met by the network while transporting a data flow. Such service requirements include delay and available bandwidth.
Accordingly, QoS-based routing is a routing mechanism under which paths for flows are determined based on some knowledge of resource availability in the network, as well as the QoS requirement of flows. The resource availability includes metrics also for delay and available bandwidth.
Present plans to implement QoS based routing intend to account for various QoS metrics, for example bandwidth, delay, and packet loss.
Traditionally packet loss is measured in the prior art as simply a rate W, from Equation (1):W=(# of lost packets)/(total # of packets)  Equation (1)
Rate W is determined by counting total numbers of packets, in gross quantities. Then W is imparted in the QoS computation. The higher the W, the lower the computed quality of service (QoS).
Packet loss at a node is now described in more detail. It will be appreciated that packet loss is intimately associated with congestion at a node.
Referring again to FIG. 2, if node N is congested, more packets will arrive than the queue 230 has capacity for. In that case, the additional packets are discarded (“lost”, or “dropped”).
Referring now to FIG. 3, a diagram is shown of packets received sequentially at the router of FIG. 2. Those stored and retransmitted are shown as clear, while those dropped are shown with an “X” through them.
Losing discarded packets due to network congestion is an expected occurrence. There have been successfully implemented backup measures, in at least two main types of situations.
In the first type, protocols that require all packets to be sent have a backup measure for ensuring that each packet has been sent. When a packet is discarded, its loss is traced, and the packet is sent again. This results in duplication of effort, because the packet was routed to a congested node in the first place.
In the second type, real time transmission protocols tolerate losing discarded packets. These protocols include applications for Voice over Internet Protocol (“VoIP”) and Video over IP. Packets that are lost will be replicated by redundancy algorithms, to conceal the lost packets. These only work decreasingly well, as more packets are lost.
Addressing packet loss for QoS only in terms of the W of Equation (1) is inadequate. That is because the computation of Equation (1) makes an assumption that packets will be lost uniformly in time.
That is not true, however. Packet loss is not distributed uniformly in time, but it tends to come in bursts, or groups, which affect perceived quality of service disproportionately. While the burstiness or uniformity affects the average W of equation (1) only a little, it affects the network performance more dramatically.
In the first type of situations, it may be less wasteful when whole groups of packets are retransmitted due to loss, instead of a few packets here and there.
In the second type of situations, the resulting quality of the reconstructed image and/or voice will be affected. That is because packet loss concealment algorithms work far better when packet loss is uniform than bursty.